package q869_reorderedPowerOf2;

import java.util.Arrays;

public class Solution {
    boolean[] vis;
    /*
    此题使用最简单的思路即为：
    1 n的所有位置的数字能够组成哪些排列
    2 这些排列中有没有属于2的幂的数字
    分别利用到
    1 全排列Ⅱ （47题）
    2 判断2的幂次
     */
    public boolean reorderedPowerOf2(int n) {
        char[] nums = Integer.toString(n).toCharArray();
        Arrays.sort(nums);
        vis = new boolean[nums.length];
        return dfs(nums, 0, 0);
    }

    private boolean dfs(char[] nums, int beginIdx, int curNum) {
        if (beginIdx == nums.length) return isVaild(curNum);
        for (int i = 0; i < nums.length; i++) {
            // 按照全排列的方式
            // 1 先判断是否有前导零
            // 2 判断是否已经使用过
            // 3 出现相同字符
            if ((curNum == 0 && nums[i] == '0') || vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) continue;
            vis[i] = true;
            if (dfs(nums, beginIdx + 1, curNum * 10 + nums[i] - '0')) return true;
            vis[i] = false;

        }
        return false;
    }

    /*
    判断一个数字是否为2的幂 只需要判断其二进制是不是只有一个1就可以了
     */
    private boolean isVaild(int curNum) {
        return (curNum & (curNum - 1)) == 0;
    }
}
